CRC is widely employed in digital communication and storage systems. CRC is a type of checksum used to detect errors in a transmitted sequence of data, called an input message.
CRC is based on a division of a polynomial H(x) over a binary finite field GF(2). A so-called generator polynomial G(x)=xngn-1xn-1+ . . . +g2x2+g1x+g0 is selected to define an n-bit CRC (“CRC-n”). Input bits of the input message are considered as coefficients of H(x) over GF(2). H(x) is then divided by G(x). The coefficients of the remainder polynomial become the bits of the CRC.
A straightforward CRC circuit employs a single linear feedback shift register (see, e.g., U.S. Pat. No. 6,295,626, which issued to Nair, et al., on Sep. 25, 2001, entitled “Symbol Based Algorithm for Hardware Implementation of Cyclic Redundancy Check”). Unfortunately, since this circuit processes the input message only one bit at a time, the input message must be serially streamed to the circuit to generate a CRC. Consequently, generation of a CRC requires as many clock cycles as the input message has bits. Most digital communication and storage applications employ input messages that are too long for this simple CRC circuit to be practical.
U.S. Pat. No. 6,295,626 discloses a way to process multiple bits of the input message at a time. According to U.S. Pat. No. 6,295,626, it is possible to build a hardware module Mk that generates a CRC for k bits of an input message at a time. The module Mk receives a k-bit-wide input value A (a current message word) and an n-bit-wide input value R (a current value of the remainder) and produces an n-bit-wide value Z (a new value of the remainder). The maximum logic depth of the module Mk is only log2(n+k) levels. Consequently, CRC calculation using such a module is faster than with linear feedback shift register.
A single instance of the module Mk, having its output connected to its first input, may be used to calculate CRCs if the total input message size m is evenly divisible by the module input width k. For example, if every input message is guaranteed to contain exactly 64×p bits, p being an arbitrary integer, a single module M54 receiving exactly 64 bits of the input message every clock cycle can suitably implement a CRC circuit.
However, many applications in which CRC generation may be required cannot guarantee that the input message size m is evenly divisible by the CRC module input width k. Stated another way, a single module Mk cannot produce a CRC for an input message having a size m, where m is not an even multiple of k. For all input messages for which m is not an even multiple of k, the last piece of the input message received by the module Mk will be less than k, and the module Mk will produce an incorrect CRC.